#ifndef BINARYSEARCH_H
#define BINARYSEARCH_H
#include <QVector>

template <typename T>
class BinarySearch
{
public:
    BinarySearch();
    ~BinarySearch();

    int binarySearch(T *numArr, int n, T target, QVector<QString> &strVector);
    int binarySearchDigui(T *numArr, int low, int high, T target, QVector<QString> &strVector);

    T *getArr();
    void setArr(T *arr);
    T getTarget();
    void setTarget(T &target);
    int getArrLen();
    void setArrLen(const int &arrLen);
private:
    int m_ArrLen;
    T *m_Arr;
    T m_Target;
};

#endif // BINARYSEARCH_H

/*模板类的定义与实现需要在同一个文件中*/
template <typename T> BinarySearch<T>::BinarySearch()
{
}


template <typename T> BinarySearch<T>::~BinarySearch()
{
    delete[] m_Arr;
}

template <typename T>
T *BinarySearch<T>::getArr()
{
    return  this->m_Arr;
}

template<typename T>
T BinarySearch<T>::getTarget()
{
    return this->m_Target;
}

template<typename T>
void BinarySearch<T>::setArr(T* arr)
{
    this->m_Arr = arr;
}

template<typename T>
void BinarySearch<T>::setTarget(T &target)
{
    this->m_Target = target;
}

template<typename T>
int BinarySearch<T>::getArrLen()
{
    return this->m_ArrLen;
}

template<typename T>
void BinarySearch<T>::setArrLen(const int &arrLen)
{
    this->m_ArrLen = arrLen;
}

template<typename T>
int BinarySearch<T>::binarySearch(T* numArr, int n, T target, QVector<QString> &strVector)
{
    int low = 0, high = n - 1, middle = 0;

    strVector.push_back("【BinarySearch Peocess 】low: " + QString::number(low) + " middle: "+ QString::number(high) + " high: "+QString::number(high));

    while(low < high)
    {
        middle = (low + high)/2;
        if(target == numArr[middle])
        {
            return middle;
        }
        else if(target < numArr[middle])
        {
            high = middle-1;
        }
        else if(target > numArr[middle])
        {
            low = middle + 1;
        }
        strVector.push_back("low: " + QString::number(low) + " middle: "+ QString::number(high) + " high: "+QString::number(high));
    }

    return -1;
}

template<typename T>
int BinarySearch<T>::binarySearchDigui(T* numArr, int low, int high, T target, QVector<QString> &strVector)
{
    int middle = (low + high) / 2;
    strVector.push_back("【BinarySearch Peocess 】low: " + QString::number(low) + " middle: "+ QString::number(high) + " high: "+QString::number(high));
    if(low > high)
    {
        return -1;
    }

    if(target == numArr[middle])
    {
        return  middle;
    }

    if(target < numArr[middle])
    {
        return binarySearchDigui(numArr, low, middle-1, target, strVector);
    }

    if(target > numArr[middle])
    {
        return binarySearchDigui(numArr, middle+1, high, target, strVector);
    }

    return -1;
}

